#pragma once

#include <unordered_map>
#include <vector>
#include <algorithm>


class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_ufs(n, -1)
	{}

	size_t FindRoot(int x)
	{
		int root = x;
		while (_ufs[root] >= 0)
		{
			root = _ufs[root];
		}
		return root;
	}

	void Union(int x1, int x2)
	{
		size_t root1 = FindRoot(x1);
		size_t root2 = FindRoot(x2);

		if (root1 != root2)
		{
			if (abs(_ufs[root1]) < abs(_ufs[root2]))
				std::swap(root1, root2);

			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
		}
	}

	size_t SetCount()
	{
		int count = 0;
		for (auto i : _ufs)
		{
			if (i < 0)
				++count;
		}
		return count;
	}

private:
	std::vector<int> _ufs;
};



